{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TopN:\n",
    "    def parent(self,n):\n",
    "        #父节点下标\n",
    "        return int((n-1)/2)\n",
    "    def left(self,n):\n",
    "       # 左节点下标\n",
    "        return 2*n+1\n",
    "    # 右节点下标\n",
    "    def right(self,n):\n",
    "        return 2*n+2\n",
    "    # 构建小顶堆保证左右子节点小于其父节点\n",
    "    def MinTopTree(self,n,data):\n",
    "        for i in range(1,n):\n",
    "            j = i\n",
    "            while j!=0 and data[j]<data[self.parent(j)]:\n",
    "                temp = 0\n",
    "                temp = data[self.parent(j)]\n",
    "                data[self.parent(j)] = data[j]\n",
    "                data[j] = temp\n",
    "                j = self.parent(j)\n",
    "        return data\n",
    "    # 将其他值与最小顶推比较替换data[0]值\n",
    "    def ReMinTopTree(self,size,n,data):\n",
    "        #data = self.MinTopTree(n,data)\n",
    "        for i in range(n,size):\n",
    "            if data[i]>data[0]:\n",
    "              #  temp = 0\n",
    "                temp = data[0]\n",
    "                data[0] = data[i]\n",
    "                data[i] = temp\n",
    "                t = 0\n",
    "                #(data[t]>data[self.right(t)] and self.right(t)<n) or (data[t]>data[self.left(t)] and data[self.left(t)]<n)这样会越界\n",
    "                #(self.left(t) < n and data[self.left(t)] < data[t]) or (self.right(t) < n and data[self.right(t)] < data[t])\n",
    "                while ((self.left(t) < n and data[self.left(t)] < data[t]) or (self.right(t) < n and data[self.right(t)] < data[t])):\n",
    "                    # 替换右孩子\n",
    "                    if data[self.right(t)]<data[self.left(t)] and self.right(t)<n:\n",
    "                        #temp = 0\n",
    "                        temp = data[t]\n",
    "                        data[t] = data[self.right(t)]\n",
    "                        data[self.right(t)] = temp\n",
    "                        t = self.right(t)\n",
    "                        \n",
    "                    else:\n",
    "                       #替换左孩子\n",
    "                        # temp = 0\n",
    "                        temp = data[t]\n",
    "                        data[t] = data[self.left(t)]\n",
    "                        data[self.left(t)] = temp\n",
    "                        t = self.left(t)\n",
    "                        \n",
    "        return data\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 17, 9, 21, 28, 19, 10, 30, 27, 6, 44, 20]\n",
      "[19, 21, 20, 44, 28, 27, 30, 1, 9, 6, 10, 17]\n"
     ]
    }
   ],
   "source": [
    "top = TopN()\n",
    "data = [21,1,10,17,28,19,9,30,27,6,44,20]\n",
    "r1 = top.MinTopTree(7,data)\n",
    "print(r1)\n",
    "r2 = top.ReMinTopTree(n=7,size=12,data=r1)\n",
    "print(r2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
